import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

// 牛客解法，最终版
public class Solution {
    public static void main(String[] args) {
        int[][] emel = new int[][]{{1, 1, 1}, {1, 2, 2}, {1, 3, 2}, {2, 1}, {1, 4, 4}, {2, 2}};
        System.out.println(Arrays.toString(LRU(emel, 3)));
    }

    public static int[] LRU(int[][] operators, int k) {
        // write code here
        LRU lru = new LRU(k);
        ArrayList<Integer> ans = new ArrayList<>();
        for (int[] temp : operators) {
            if (temp[0] == 1) {
                lru.set(temp[1], temp[2]);
            } else if (temp[0] == 2) {
                ans.add(lru.get(temp[1]));
            }
        }
        int[] res = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            res[i] = ans.get(i);
        }
        return res;

    }

    static class LRU {
        static class Node {
            public int value;
            public int key;
            public LRU.Node prev;
            public LRU.Node next;
        }

        private int k;
        private Map<Integer, LRU.Node> map;
        private LRU.Node hair;
        private LRU.Node shoe;

        private int capacity;

        LRU(int k) {
            this.capacity = k;
            this.map = new HashMap<>();
            this.k = 0;
            this.hair = new LRU.Node();
            this.shoe = new LRU.Node();
            hair.next = shoe; // 注意这里初始化
            shoe.prev = hair;
        }

        public void set(int key, int value) {
            if (map.containsKey(key)) {
                LRU.Node node = map.get(key);
                node.value = value;
                moveToHead(node);
            } else {
                LRU.Node node = new LRU.Node();
                node.key = key;
                node.value = value;
                if (k >= capacity) removeTail();
                insertToHead(node);
            }
        }

        public int get(int key) {
            if (!map.containsKey(key)) return -1;
            LRU.Node node = map.get(key);
            moveToHead(node);
            return node.value;
        }

        private void moveToHead(LRU.Node node) {
            delete(node);
            insert(node, hair);
        }

        private void removeTail() {
            map.remove(shoe.prev.key);
            k--; //先写变化
            delete(shoe.prev);
        }

        private void insertToHead(LRU.Node node) {
            k++; // 先写k等的变化
            map.put(node.key, node);
            insert(node, hair);
        }

        private void delete(LRU.Node node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }

        private void insert(LRU.Node node, LRU.Node pre) {
            node.next = pre.next;
            pre.next.prev = node;
            pre.next = node;
            node.prev = pre;
        }
    }
}
